#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int maxn = 2e3 + 10;
int n,m;
int ist[30], del[30];
string s;

int dp[maxn][maxn];

void solve(){
	cin >>n>>m;
	cin>>s;
	for(int i=1;i<=n;i++){
		char c;
		int a,b;
		cin>>c>>a>>b;
		ist[c-'a']=a;
		del[c-'a']=b;
	}
	
	s="0"+s;
	
	
	memset(dp, 0x3f, sizeof(dp));
	
	for (int i=1;i<=m;i++) {
		dp[i][i]=0;
	}
	
	dp[0][0]=dp[0][1]=0;
	
	// 进行区间 DP
	for(int len=2;len<=m;len++) {
		for(int i=1,j=len;j<=m;i++, j++){
			if (s[i]==s[j]) {
				if (len==2) { // 这里不要忘了对 len=2 进行特殊判断
					dp[i][j]=0; 
				} else {
					dp[i][j]=dp[i+1][j-1];
				}
			} else {
				// 处理 i 位置元素
				dp[i][j]=dp[i+1][j]+min(del[s[i]-'a'], ist[s[i]-'a']); // 删除或者右边添加
				// 处理 j 位置元素
				dp[i][j]=min(dp[i][j], dp[i][j-1]+min(del[s[j]-'a'], ist[s[j]-'a']));
			}
			
		}
	}
	cout << dp[1][m]<<'\n';
	
}

signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}
